정보 없는 검색이란 실세계의 환경적 정보가 반영되지 않는다. 주어진 상태가 목표 상태와 가까운지 먼지에 대해 추론할 수 없다. 즉, 목표 상태를 찾아내는 데에 직관적 정보를 활용할 수 없다. 예컨대 지도상의 한 지점에서 목표까지 얼마나 남았는지에 대해 알아볼 수 없다면, 우리는 목표로 가는길과 정반대의 길마저도 검색하는 수고를 들여야 할 수도 있다. 요는, 목표상태를 찾아내기만 하는 것이 아니라, 목표 상태에 이르는 효율적인 경로를 찾아내는 데에 있다.
즉, 검색트리상에서 최적해를 찾는 것을 의미한다.

Search Tree

검색트리의 임의 노드를 읽고, 가능한 동작에 따른 자식 노드들을 생성generation하는 것을 확장expansion이라 한다. 이때의 자식 노드를 후행자 노드successor node라고 한다.

이 후행자 노드들은 생성되었지만 확장되지 않은 상태이며, 확장의 후보로서 간주된다. 이러한 후보들은 Priority Queue를 통해 검색 순서를 정한다. 따라서 검색의 최전선에서 대기하고 있기 때문에 전선frontier이라고 부른다. (cs188 강의에서는 fringe라고 한다.)

State Space Graph vs Search Tree

검색트리search tree의 노드는 상태state를 포함하지만, 상태는 아니며, 그 상태에 도달할 때까지의 경로path를 포함하는 정보이다. 따라서 상태공간과 검색공간은 서로 다른 것이며, 검색트리는 한정된 상태공간으로부터 무한하게 확장될 수 있다. #Q 그런데 검색공간이 검색트리의 노드들을 일컫는게 맞나? - 맞는듯?

Search Algorithms

검색을 하기 위해서는 적절한 검색 알고리즘이 있어야 할것이다. 어떤 검색 알고리즘이 유리한가를 따지기 위해서는 먼저 검색 알고리즘이 무엇을 가리키는 것인지에 대해 고민해야 한다.

검색 알고리즘이란 전선, 즉 우선순위 큐의 우선순위 결정 기준을 정의하는 방식이다.

이는 검색트리 각 노드의 우선권을 결정하는 함수 f(n)에 대한 수식으로 표현된다.

다음과같이 3가지 기본방식이 있다.

• BFS(Breadth-First Search)
• UCS(Uniform-Cost Search)
• DFS(Deep-First Search)

BFS(Breadth-First Search)

가장 먼저, 너비 우선 검색이 있다.
이 말은 한 레벨의 노드들을 모두 검색하고, 그 다음 레벨로 내려간다는 의미이다.
우선권은 낮은 깊이에 있고 전선은 일반 FIFO 큐로도 구현가능하다.

알고리즘 성능 평가

• 완결성: O
• 최적해보장: O (오직 모든 동작의 비용이 동일하다고 가정할 때에만)
• 시간복잡도: $1+b+b^2+...+b^s=O(b^s)$
• 공간복잡도: $O(b^s)$
  ※ 공간복잡도는 대기열(전선)에서 대기하는 후행자 노드들이다.

이 알고리즘의 공간복잡도는 시간복잡도보다 더 큰 문제이다.
만약, 분기계수 b = 10일 때, 해답 노드가 깊이 s = 10에 있고, 메모리 요구량은 노드당 1kB, 처리속도는 초당 백만노드일 때, 해답을 얻는 데 걸리는 시간은 3시간 미만이지만, 메모리는 10테라바이트가 필요하다. 물론 속도도 여전히 문제이다. s =14일 땐, 메모리가 무한하더라도 문제를 해결하는 데 3.5년이 걸린다.

UCS(Uniform-Cost Search)

다음으로 균일 비용 검색이 있다.
이는 너비 우선 검색과 유사한 느낌이 있다. 너비 우선 검색은 동일한 깊이를 훑고 내려갔다. 이것은 동일한 비용을 훑고 다음 비용으로 간다.
우선권은 낮은 비용에 있다.

f(n) = 초기 상태에서 현재 상태까지 경로상의 누적비용 (낮은 것 우선)

알고리즘 성능 평가

• 완결성: O
• 최적해보장: O
• 시간복잡도: $O(b^{C^{\ast }/ϵ})$
• 공간복잡도: $O(b^{C^{\ast }/ϵ})$

시간복잡도와 공간복잡도가 여전히 문제라는 것은, 그림만으로도 알 수 있다. 저런식으로 한층 한층 탐색해 나가기 때문이다.

DFS(Deep-First Search)

마지막으로, 깊이 우선 검색이 있다.
우선권은 깊이의 크기가 큰 것에 있다. 스택으로도 구현된다.

f(n) = 깊이 (큰 것 우선)

위 그림처럼 갈 수 있는 가장 깊은 곳(최대 깊이 m)까지 우선적으로 탐색이 이뤄진다.

알고리즘 성능 평가

• 완결성: O (단, 무한상태공간일 때는 X)
• 최적해보장: X
• 시간복잡도: $O(b^m)$
• 공간복잡도: $O(bm)$

이 알고리즘의 장점은 메모리를 훨씬 덜 요구한다는 것이다. 일을 죄다 벌려놓고 수습하는 너비우선검색과 달리, 깊이우선은 한우물만을 파기 때문에, (분기계수) x (최대 깊이) 수준의 메모리만을 요구할 뿐이다.

하지만, 여전히 시간복잡도는 해결되지 않았다.

Others

IDFS

DFS의 단점을 보완하기 위해, level threshold를 1씩 올려가며 DFS를 반복 수행한다.

Bidirectional Search(양방향 검색)

이것은 기존의 순방향 검색과 목표에서 출발하는 역방향 검색을 모두 이용하여 획기적으로 비용을 줄이는 방식이다.
이것은 $b^{m/2}+b^{m/2}<<b^m$이기 때문에 비용이 획기적으로 줄어든다.